class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //完全背包问题，
        //dp[i][j]代表从前i个硬币中进行选择，总金额等于j时的最少硬币个数为多少
        //状态转移方程：
        //dp[i][j]对于第i个硬币我可以不选择dp[i-1][j]
        //也可以选择1个两个或者多个
        //dp[i][j] = dp[i][j-i]+1
        //j-coins[i]<=amount
        //dp[i][j] = min(dp[i][j],dp[i][j-amount[i]]+1)
        //初始化依旧是多一行和多一列
        //第一行我没有硬币出了j = 0时此时的个数为0其余的都是不可选择全部为无穷大
        //第一列代表我有无穷个硬币但是总和为0依旧时dp[0][0] = 0其余的都是+无穷
        int n = coins.size();
        vector<vector<int>> dp(n+1,vector<int>(amount+1,0));
        //将第一列和第一行初始化为正无穷出了dp[0][0]
        for(int j = 1;j<=amount;j++)
        {
            dp[0][j] = 0x7f7f7f7f;
        }
        for(int i = 1;i<=n;i++)
        {
            dp[i][0] = 0x7f7f7f7f;
        }
        dp[0][0] = 0;
        for(int i = 1;i<=n;i++)
        {
            for(int j = 0;j<=amount;j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j-coins[i-1]<=amount&&j-coins[i-1]>=0)
                {
                    dp[i][j] = min(dp[i][j],dp[i][j-coins[i-1]]+1);
                }
            }
        }
        return dp[n][amount] == 0x7f7f7f7f?-1:dp[n][amount];
    }
};//第一种没有使用记忆化数组进行优化
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 完全背包问题，
        // dp[i][j]代表从前i个硬币中进行选择，总金额等于j时的最少硬币个数为多少
        // 状态转移方程：
        // dp[i][j]对于第i个硬币我可以不选择dp[i-1][j]
        // 也可以选择1个两个或者多个
        // dp[i][j] = dp[i][j-i]+1
        // j-coins[i]<=amount
        // dp[i][j] = min(dp[i][j],dp[i][j-amount[i]]+1)
        // 初始化依旧是多一行和多一列
        // 第一行我没有硬币出了j = 0时此时的个数为0其余的都是不可选择全部为无穷大
        // 第一列代表我有无穷个硬币但是总和为0依旧时dp[0][0] = 0其余的都是+无穷
        int n = coins.size();
        vector<int> dp(amount+1,0);
        //将第一列和第一行初始化为正无穷出了dp[0][0]
        for(int j = 1;j<=amount;j++)
        {
            dp[j] = 0x7f7f7f7f;
        }
        dp[0] = 0;
        for(int i = 1;i<=n;i++)
        {
            for(int j = 0;j<=amount;j++)
            {
                if(j-coins[i-1]<=amount&&j-coins[i-1]>=0)
                {
                    dp[j] = min(dp[j],dp[j-coins[i-1]]+1);
                }
            }
        }
        return dp[amount] == 0x7f7f7f7f?-1:dp[amount];
    }
};//使用记忆化数组进行优化